设计一个网络爬虫需要考虑哪些因素？
在互联网增长速度趋于稳定的今天，许多大厂已将面试重心从八股文转向场景题，也就是系统设计，强调应聘者在实际工作环境中的解决问题能力。这就是我推出的系统设计系列的初衷，专注于系统设计的深度学习和面试技巧。在这个系列中，提供大量真实的系统设计场景题，以及高效的解决方案。无论您是初学者还是资深从业者，都能在这里得到宝贵的知识和经验。点击关注
让我们设计一个网络爬虫，它可以系统性地浏览和下载万维网(World Wide Web)的内容。网络爬虫也被称为网络蜘蛛、机器人、虫子、行走者和机器人。
难度等级：困难
1. 什么是网络爬虫？
网络爬虫是一个软件程序，它以一种有条理且自动化的方式浏览万维网。它通过递归获取一组起始页面的链接来收集文档。许多网站，尤其是搜索引擎，使用网络爬行作为提供最新数据的手段。搜索引擎下载所有页面，以在其上创建索引，以实现更快的搜索。
网络爬虫的一些其他用途包括：
• 测试网页和链接的有效语法和结构。
• 监视网站以查看其结构或内容何时更改。
• 为热门网站维护镜像站点。
• 寻找侵犯版权的行为。
• 建立特定目的的索引，例如，一个理解存储在网络上的多媒体文件内容的索引。
2. 系统的要求和目标
假设我们需要爬取整个网络。
可扩展性：我们的服务需要具有可扩展性，使其能够爬取整个网络，并且可以用来获取数亿份网页文档。
可扩展性：我们的服务应以模块化的方式设计，预期会添加新功能。未来可能需要下载和处理新的文档类型。
3. 一些设计考虑
爬取网络是一项复杂的任务，有许多方法可以实现。在进一步之前，我们应该提出一些问题：
它只是一个HTML页面的爬虫吗？还是我们应该获取和存储其他类型的媒体，如声音文件、图片、视频等？这很重要，因为答案可能会改变设计。如果我们正在编写一个通用的爬虫来下载不同类型的媒体，我们可能希望将解析模块分解为不同的模块集：一个用于HTML，一个用于图像，或者另一个用于视频，其中每个模块都提取该媒体类型的有趣内容。
现在我们先假设我们的爬虫只处理HTML，但它应该是可扩展的，方便添加对新媒体类型的支持。
我们要看哪些协议？HTTP吗？FTP链接呢？我们的爬虫应该处理哪些不同的协议？为了练习，我们假设是HTTP。同样，扩展设计以便以后使用FTP和其他协议并不难。
我们预计会爬取多少页面？URL数据库会变得多大？我们假设需要爬取十亿个网站。由于一个网站可能包含很多URL，我们假设我们的爬虫将到达的不同网页的上限为150亿。
什么是‘RobotsExclusion(机器人排除协议)’，我们应该如何处理它？礼貌的网络爬虫会实现Robots Exclusion Protocol，该协议允许网站管理员声明他们的网站的某些部分对爬虫是禁止的。Robots Exclusion Protocol要求网络爬虫在从网站下载任何实质性内容之前，先获取一个名为robot.的特殊文档，该文档包含这些声明。
4. 容量估算和限制
如果我们想在四周内爬取150亿个页面，我们需要每秒获取多少个页面？
15B / (4周 * 7天 * 86400秒) ~= 6200页/秒那么存储空间呢？页面大小变化很大，但是，如上所述，由于我们只处理HTML文本，我们假设平均页面大小为100KB。如果我们在每个页面上存储500字节的元数据，我们需要的总存储空间是：
15B * (100KB + 500) ~= 1.5 petabytes(1.5PB)假设70%的容量模型（我们不想超过我们存储系统总容量的70%），我们需要的总存储空间是：
1.5 petabytes / 0.7 ~= 2.14 petabytes(2.14PB)5. 高级设计
任何网络爬虫执行的基本算法都是以一列种子URL为输入，反复执行以下步骤。
1. 从未访问的URL列表中选择一个URL。
2. 确定其主机名称的IP地址。
3. 建立与主机的连接以下载相应的文档。
4. 解析文档内容以寻找新的URL。
5. 将新的URL添加到未访问的URL列表中。
6. 处理下载的文档，例如，存储它或索引其内容等。
7. 返回到步骤1
如何爬取?
广度优先还是深度优先？通常使用广度优先搜索(BFS)。然而，深度优先搜索(DFS)在某些情况下也被利用，例如，如果你的爬虫已经与网站建立了连接，它可能只是DFS网站内的所有URL，以节省一些握手开销。
路径上升爬取：路径上升爬取可以帮助发现许多孤立的资源或者在常规爬取特定网站时不会发现的入站链接的资源。在这个方案中，爬虫会上升到它打算爬取的每个URL的每个路径。例如，当给定一个种子URL http://foo.com/a/b/page.html，它会尝试爬取/a/b/，/a/和/。
在实现高效网络爬虫时的困难
有两个网络的重要特性使得网络爬取成为一个非常困难的任务：
1. 大量的网页：大量的网页意味着网络爬虫在任何时候只能下载一部分网页，因此，网络爬虫应该足够智能以优先进行下载。
2. 网页的更改速度。在今天动态世界的另一个问题是互联网上的网页变化非常频繁。因此，当爬虫从一个网站下载最后一页时，该页可能已经改变，或者可能已经添加到网站上了。
一个最基本的爬虫至少需要以下组件：
1. URL前线：存储要下载的URL列表，并确定哪些URL应该优先被爬取。
2. HTTP获取器：从服务器检索网页。
3. 提取器：从HTML文档中提取链接。
4. 重复消除器：确保同样的内容不会被无意中提取两次。
5. 数据存储：存储检索到的页面、URL和其他元数据。
6. 详细组件设计
假设我们的爬虫在一个服务器上运行，所有的爬取工作都由多个工作线程完成，每个工作线程执行所有需要下载和处理文档的步骤。
这个循环的第一步是从共享的URL前线中移除一个绝对URL以进行下载。一个绝对URL以一个方案（比如，"HTTP"）开头，该方案标识应该用来下载它的网络协议。我们可以以模块化的方式实现这些协议，以便扩展，这样，如果我们的爬虫以后需要支持更多的协议，可以轻松实现。基于URL的方案，工作线程调用相应的协议模块下载文档。下载后，文档被放入文档输入流（DIS）。将文档放入DIS会使其他模块能够多次重新读取文档。
一旦文档被写入DIS，工作线程调用去重测试，以确定是否之前已经看过这个文档（与另一个URL关联）
如果是，文档不再进行任何处理，工作线程从前线移除下一个URL。
接下来，我们的爬虫需要处理下载的文档。每个文档可能有不同的MIME类型，如HTML页面，图片，视频等。我们可以以模块化的方式实现这些MIME方案，这样，如果我们的爬虫以后需要支持更多类型，我们可以轻松实现。基于下载文档的MIME类型，工作线程调用与该MIME类型关联的每个处理模块的处理方法。
此外，我们的HTML处理模块将从页面中提取所有链接。每个链接被转换为绝对URL，并通过用户提供的URL过滤器进行测试，以确定是否应下载。如果URL通过了过滤器，工作线程执行URL已看见的测试，这将检查URL是否被看见过，也就是，它是否在URL前线或已被下载。如果URL是新的，它被添加到前线。
让我们逐一讨论这些组件，看看它们如何被分布到多台机器上：
1. URL前线：URL前线是包含所有待下载URL的数据结构。我们可以通过广度优先遍历Web，从种子集中的页面开始进行爬取。这种遍历可以很容易地通过使用FIFO队列实现。
由于我们有大量的URL需要爬取，我们可以把我们的URL前线分布到多个服务器上。假设在每个服务器上我们都有多个工作线程进行爬取任务。我们还假设我们的哈希函数将每个URL映射到一个将负责爬取它的服务器。
在设计分布式URL前线时，必须记住以下礼貌要求：
1. 我们的爬虫不应该通过从中下载大量页面来使服务器过载。
2. 我们不应该让多台机器连接一个Web服务器。
为了实现这种礼貌约束，我们的爬虫可以在每个服务器上有一组不同的FIFO子队列。每个工作线程将有自己的子队列，从中移除URL以进行爬取。当需要添加新的URL时，将其放入哪个FIFO子队列将由URL的规范主机名决定。我们的哈希函数可以将每个主机名映射到一个线程号。这两点一起意味着，最多只有一个工作线程会从给定的Web服务器下载文档，而且，通过使用FIFO队列，它不会使Web服务器过载。
我们的URL前线会有多大？大小会达到数亿个URL。因此，我们需要将我们的URL存储在磁盘上。我们可以实现我们的队列，使它们有单独的缓冲区用于入队和出队。填充后的入队缓冲区将被倾倒到磁盘上，而出队缓冲区将保持
将要访问的URL的缓存保存在URL队列中；它可以定期从磁盘中读取数据以填充缓存。
1. 获取模块( The fetcher module)：获取模块的目的是使用适当的网络协议（如HTTP）下载给定URL对应的文档。正如上文所述，网站管理员会创建robot.文件，让爬虫无法访问他们网站的某些部分。为了避免每次请求都下载这个文件，我们的爬虫的HTTP协议模块可以维护一个固定大小的缓存，将主机名映射到其机器人的排除规则。
2. 文档输入流(Document input stream)：我们的爬虫设计使得同一份文档可以被多个处理模块处理。为了避免多次下载文档，我们将文档在本地进行缓存，使用一个名为文档输入流（Document Input Stream，简称DIS）的抽象。
DIS是一个输入流，它缓存了从互联网读取的文档的所有内容。它还提供了重新读取文档的方法。DIS可以完全在内存中缓存小文档（64KB或更小），而较大的文档则可以临时写入一个备份文件。
每个工作线程都有一个关联的DIS，它在文档与文档之间进行复用。在从边界提取URL后，工作线程将该URL传递给相关的协议模块，该模块通过网络连接初始化DIS，以包含文档的内容。然后，工作线程将DIS传递给所有相关的处理模块。
1. 文档去重测试(Document Dedupe test)：在网络上，许多文档都可以通过多个不同的URL获取。也有很多情况下，文档会在各种服务器上镜像。这些效应都会导致任何网络爬虫多次下载同一份文档。为了防止对文档进行多次处理，我们对每个文档进行一次去重测试，以消除重复。
为了进行这个测试，我们可以计算每个处理过的文档的64位校验和，并将其存储在数据库中。对于每一个新的文档，我们可以比较其校验和和所有以前计算过的校验和，以查看文档是否已经被看过。我们可以使用MD5或SHA来计算这些校验和。
校验和存储有多大呢？如果我们的校验和存储的全部目的是做去重，那么我们只需要保留一个包含所有之前处理过的文档的校验和的唯一集合。考虑到有150亿个不同的网页，我们将需要：
15B * 8 bytes => 120 GB虽然这可以适应现代服务器的内存，如果我们没有足够的可用内存，我们可以在每个服务器上保持较小的LRU基础缓存，所有内容都由持久性存储支持。去重测试首先检查校验和是否存在于缓存中。如果不存在，它必须检查校验和是否存储在后端存储中。如果找到了校验和，我们将忽略这个文档。否则，它将被添加到缓存和后端存储中。
1. URL过滤器(URL filters)：URL过滤机制提供了一个定制化的方法，可以控制下载的URL集合。这是用来把网站列入黑名单，这样我们的爬虫就可以忽略它们。在将每个URL添加到边界前，工作线程会查阅用户提供的URL过滤器。我们可以定义过滤器，通过域名，前缀或协议类型来限制URL。
2. 域名解析(Domain name resolution)：在联系网络服务器之前，网络爬虫必须使用域名服务(DNS)将网络服务器的主机名映射为IP地址。考虑到我们将处理的URL数量，DNS名字解析将是我们爬虫的一个大瓶颈。为了避免重复的请求，我们可以通过建立我们的本地DNS服务器来开始缓存DNS结果。
3. URL去重测试(URL dedupe test)：在提取链接时，任何网络爬虫都会遇到多个链接到同一份文档的情况。为了避免多次下载和处理同一份文档，我们必须在将每个提取的链接添加到URL边界前，对其进行URL去重测试。
为了进行URL去重测试，我们可以存储我们的爬虫看到的所有URL。
以规范形式存储在数据库中。为了节省空间，我们不在URL集合中存储每个URL的文本表示形式，而是存储一个固定大小的校验和。
为了减少数据库存储操作的次数，我们可以在每个主机上保持一个由所有线程共享的常用URL的内存缓存。有这个缓存的原因是，链接到一些URL的链接非常常见，因此在内存中缓存常用的URL会导致较高的内存命中率。
我们需要多少存储空间来存储URL的存储呢？如果我们的校验和的整个目的是做URL去重，那么我们只需要保持一个包含所有之前看到的URL的校验和的唯一集合。考虑到150亿个不同的URL和每个校验和4字节，我们将需要：
15B * 4 bytes => 60 GB我们能用布隆过滤器来做去重吗？布隆过滤器(Bloom filters)是一种可能产生误报的概率性数据结构，用于进行集合成员测试。一个大的位向量代表了这个集合。通过计算元素的'n'个哈希函数并设置相应的位，将元素添加到集合中。如果元素的所有'n'个哈希位置的位都设置了，那么这个元素就被认为在集合中。因此，一个文档可能被错误地认为在集合中，但是不可能出现误报。
用布隆过滤器做URL已看测试的缺点是，每一个误报都会导致URL不被添加到前沿，因此，文档永远不会被下载。可以通过增大位向量来降低误报的几率。
1. 检查点(Checkpointing)：对整个网络的爬取需要几周的时间才能完成。为了防止失败，我们的爬虫可以定期将其状态的快照写入磁盘。中断或终止的爬取可以轻易地从最近的检查点重新开始。
7. 容错性
我们应该使用一致性哈希来在爬取服务器之间进行分布。一致性哈希不仅可以帮助替换死机的主机，还可以帮助在爬取服务器之间分配负载。
我们所有的爬取服务器都会进行定期的检查点操作，并将他们的FIFO队列存储到磁盘中。如果一个服务器宕机了，我们可以替换它。同时，一致性哈希应该把负载转移到其他服务器上。
8. 数据分区
我们的爬虫将处理三种数据：1）需要访问的URL 2）进行去重的URL校验和 3）进行去重的文档校验和。
由于我们是根据主机名来分配URL的，我们可以在同一主机上存储这些数据。所以，每个主机都会存储需要访问的URL集，所有之前访问过的URL的校验和，以及所有下载的文档的校验和。由于我们将使用一致性哈希，我们可以假设URL会从负载过重的主机重新分配。
每个主机将定期进行检查点操作，并将所有持有的数据的快照转储到远程服务器上。这将确保如果一个服务器宕机了，另一个服务器可以通过从最后的快照中获取其数据来替换它。
9. 爬虫陷阱
有许多爬虫陷阱，垃圾网站，和伪装的内容。爬虫陷阱是一种URL或一组URL，它们会让爬虫无限期地进行爬取。有些爬虫陷阱是无意的。例如，文件系统内的一个符号链接可以创建一个循环。其他的爬虫陷阱是有意设置的。例如，有人编写了动态生成无限网络文档的陷阱。这些陷阱背后的动机各不相同。反垃圾邮件陷阱是设计来捕捉寻找电子邮件地址的垃圾邮件发送者使用的爬虫的，而其他网站使用陷阱来捕捉搜索引擎爬虫以提高他们的搜索排名。
推荐阅读
你好，我是拾叁，7年开发老司机、互联网两年外企5年。怼得过阿三老美，也被PR comments搞崩溃过。这些年我打过工，创过业，接过私活，也混过upwork。赚过钱也亏过钱。一路过来，给我最深的感受就是不管学什么，一定要不断学习。只要你能坚持下来，就很容易实现弯道超车！所以，不要问我现在干什么是否来得及。如果你还没什么方向，可以先关注我，这里会经常分享一些前沿资讯和编程知识，帮你积累弯道超车的资本。